package LeetCode;
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合

import java.util.*;

public class Num20 {
    public boolean isValid(String s) {
        //自己做
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        //将字符串转为字符输出
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            //遇见左括号直接入栈
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else {
                //此时为右括号
                if (stack.isEmpty()) {
                    //如果栈为空，第一个字符为右括号，那就没有左括号匹配
                    return false;
                }
                //匹配左括号，弹出左括号
                char top = stack.pop();
                if (c == '}' && top != '{') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
                if (c == ')' && top != '(') {
                    return false;
                }
            }
        }
        //此时字符串扫描完毕，判断当前栈中是否为空
        return stack.isEmpty();
        //利用栈加Map类完成
//        int n = s.length();
//        if (n % 2 == 1) {
//            return false;
//        }
//
//        Map<Character, Character> pairs = new HashMap<>() {{
//            put(')', '(');
//            put(']', '[');
//            put('}', '{');
//        }};
//        Deque<Character> stack = new LinkedList<>();
//        for (int i = 0; i < n; i++) {
//            char ch = s.charAt(i);
//            if (pairs.containsKey(ch)) {
//                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
//                    return false;
//                }
//                stack.pop();
//            } else {
//                stack.push(ch);
//            }
//        }
//        return stack.isEmpty();
    }
}
